<html>
<!-- $LastChangedDate: 2010-12-14 12:53:12 -0500 (Tue, 14 Dec 2010) $ -->
<!-- Copyright (C) 2004,2009 Jim Brooks http://www.palomino3d.org -->
<head>
<title>Palomino - Collision-Detection Module</title>
<link rel='stylesheet' type='text/css' href='docs.css'>
<link rel='icon' type='image/png' href='images/favicon.png'/>
</head>
<body>

<!-- ----------------------------------------------------------------------- -->
<h1>Palomino - Collision-Detection Module</h1>
<p>
&copy;2004,2009&nbsp;&nbsp;Jim E. Brooks
&nbsp;&nbsp;<a href='http://www.palomino3d.org'>http://www.palomino3d.org</a>
</p>
<hr>
<ul>
  <li><a href='index.html'>Index</a></li>
  <li><a href='#Flaws'>Flaws</a></li>
  <li><a href='#Overview'>Overview</a></li>
      <ul>
        <li><a href='#Collision vs. Crash'>Collision vs. Crash</a></li>
      </ul>
  <li><a href='#Implementation'>Implementation</a></li>
  <li><a href='#OSG Ray Intersection'>OSG Ray Intersection</a></li>
  <li><a href='#Safe Contact'>Safe Contact</a></li>
</ul>

<!-- ----------------------------------------------------------------------- -->
<hr>
<a name='Flaws'></a>
<h2>Flaws</h2>
<p><!--date-->[2010/12]</p>
<p>
A known flaw is that every collidable is tested against every other one,
resulting in redundant testing.
</p>
<p>For Objects { A, B, C }, testing should iterate as a <i>mathematical combination</i>
<br>where a tested Object is removed from further testing:
<br>combination: AB, AC, BC
<br>inefficient: AB, AC, BA, BC, CA, CB
<br>AB and BA are redundant.
</p>

<!-- ----------------------------------------------------------------------- -->
<hr>
<a name='Overview'></a>
<h2>Overview</h2>
<p><!--date-->[2010/05]</p>
<p>
The Collision class abstracts the exact collision-detection algorithm.
It is passed a Dyna and determines if it has collided into another Object.
Dyna objects have a Dyna::Tick() method which executes collision-detection.
</p>
<p>
Collision-detection is done when Tick() is called because
that is the place where a Dyna will be animated.
SetMatrix() isn't the reliable place to do collision-detection,
because it could be bypassed, for example, SetPosition() could be implemented
to directly change the matrix.
</p>
<a name='Collision vs. Crash'></a>
<h3>Collision vs. Crash</h3>
<p><!--date-->[2008/03]</p>
<p>
The collision module is dedicated to <i>collision-detection</i>
as opposed to <i>crash-determination</i>.
</p>
<p>
Don't confuse collision-detection with crash-determination.
A <i>collision</i> is just an intersection of graphical objects.
Determining a crash is a more complex function that
begins with collision as the first criteria,
but involves additional criteria such as physics (velocity, momentum).
</p>

<!-- ----------------------------------------------------------------------- -->
<hr>
<a name='Implementation'></a>
<h2>Implementation</h2>
<p><!--date-->[2008/08]</p>
<p>
Collision-detection is based on <a href='#OSG Ray Intersection'>OSG ray intersection</a> (osg::IntersectionVisitor).
But the algorithm is abstracted by the Collision class, which  would allow reimplementing Collision
(using BSP trees in case OSG ray intersection proves sub-optimal).
</p>
<p>
Collidable and non-collidable objects are segregated by the Collision singleton.
This is for both correctness and efficency.
Objects such as clouds and sky domes aren't collidable but might be intersected.
Collision maintains a container of collidable Objects.
Objects, via Object::SetCollidable(), informs changes in collidability to Collision.
</p>

<!-- ----------------------------------------------------------------------- -->
<hr>
<a name='OSG Ray Intersection'></a>
<h2>OSG Ray Intersection</h2>
<p><!--date-->[2008/02]</p>
<p>
Dyna objects are translated in 3D space every tick.
The starting and ending 3D points of the movement ("step") forms the ray used for testing intersection.
Note the alternative of using a positive and negative radius to form a ray across the Object's bounding sphere
would be inaccurate because the length of a step could be several times greater.
</p>
<p>
From the <a href='http://faculty.nps.edu/jasullivan/osgtutorials/osgIntersect.htm'>Naval Postgraduate School's OSG tutorial:</a>
</p>
<i>
<p>
LineSegments (osg::LineSegment) Intersection detection is based on
rays. Line segments provide a means to define these rays. Line
segments consist of two osg::Vec3 instances - one to define a start
point and one to define the end point. When invoked, intersection
detection is performed along this ray.
[..]
<br>
IntersectionVisitor: Intersection detection
tests between a ray and geometry instances in a scene are initiated by
creating and applying an intersection visitor. The intersectionVisitor
class is derived from the NodeVisitor class.
A list of line segments to use for intersection detection is maintained.
For each of these segments, a list of hits
(osgUtil::IntersectVisitor::HitList instance) is created.
</p>
</i>

<!-- ----------------------------------------------------------------------- -->
<hr>
<a name='Safe Contact'></a>
<h2>Safe Contact</h2>
<p><!--date-->[2008/02]</p>
<p>
The collision module, being graphical in nature, is separate from physics.
Collision::IfCollision() simply reports an intersection of a line and geometry.
</p>
<p>
Determining a <i>safe contact</i> shall be done externally
by combining methods of the collision and physics modules.
</p>
<pre>
Craft::Tick()
{
    mCollision = Collision::GetInstance().IfCollision( this )
    if ( mCollision )
    {

        // If descending, velocity's altitude coordinate will be negative.
        const Velocity velocity = GetCraftPhysics().ComputeVelocity();
        if ( velocity[ALT] < SAFE_LANDING_THRESHOLD )
        {
            Crash();
        }
    }
}

CraftPhysics::Tick()
{
    if ( mCraft->IfCollision() )
    {
        [add contact force]
    }
}
</pre>

<!-- ********************************* END ********************************* -->
<hr>
<p align='center'>
<font size='-2'>
<!-- hhmts start -->
Last modified: Tue Dec 14 11:39:44 CST 2010
<!-- hhmts end -->
</font>
</p>

</body>
</html>
